\section{Heur'istica Constructiva}

\subsection{Introducci'on}
Presentaremos a continuaci'on las ideas con las cuales nos basamos para realizar una heur'isitica constructiva simple y efectiva para resolver el problema MAX-SAT. Generalmente las heuristicas proporcionan reglas y estrategias, de las cuales vamos a valernos para obtener una soluci'on aceptable en un tiempo de ejecuci'on considerablemente menor al que requiere el algoritmo exacto para hallar la soluci'on 'optima. Al elegir una determinada heur'istica se esta produciendo un compromiso de costo/beneficio, es decir, cuanto tiempo uno esta dispuesto a tolerar para encontrar una mejor soluci'on. 

\subsection{Soluci'on}
Nuestra elecci'on de heur'istica constructiva se basa en un algoritmo goloso, dada la simplicidad que requieren para construir una solucion para un problema dado. Otro de los motivos por el cual nos inclinamos por esta alternativa y no por otras es que los algoritmos golosos son frecuentemente usados para generar soluciones aproximadas a una soluci'on 'optima en problemas complejos que no pueden ser resueltos de manera exacta de forma aceptable, ya que estas soluciones aproximadas son construidas r'apidamente y que generalmente pueden ser mejoradas mediante otro tipo de algoritmos un poco m'as complejos como los algoritmos de busqueda local. \\
Los algoritmos golosos trabajan en etapas, en cada etapa es tomada una decisi'on que se presenta como 'optima(para la etapa actual), sin tener en cuenta las consecuencias futuras. 
% Esta estrategia de “tomar lo que se pueda en este momento” es lo que da nombre a esta clase de algoritmos. \\
% En muchos casos esta estrateg'ia no nos llevar'a a una soluci'on 'optima correcta, sino que producir'a una soluci'on sub'opitma.\\
En el contexto de nuestro problema, nuestra soluci'on golosa se basa en la siguiente idea: \\
Ir construyendo un conjunto de literales, donde cada uno de ellos cumple ser el literal con mayor cantidad de apariciones en las cl'auslas del caso de prueba analizado. Esto lo vamos realizando en etapas, una vez que optenemos aquel literal con mayor frecuencia dentro de las cl'auslas lo agregamos al futuro conjunto soluci'on y eliminamos aquellas cl'auslas donde se encuentre dicho literal. Esto mismo lo repetimos mientras nos queden cl'auslas o variables en nuestro caso de prueba.\\ 

\newpage

\subsection{Pseudoc'odigo}
 
\newcommand{\constructivaGolosa}{\ensuremath{\mbox{\sc constructivaGolosa}}}
	\begin{algorithm}[H]
		\caption{\constructivaGolosa(CasoDePrueba casoDePrueba)}\label{alg:constructivaGolosa}
			\medskip
 			\begin{algorithmic}[1]
				\STATE cantidadDeVariablesDelCaso $\leftarrow$ casoDePrueba.cantidadVariables
				\STATE Conjunto$<$Clausula$>$ clausulasDelCaso $\leftarrow$ casoDePrueba.clausulas
				\STATE CasoDePrueba copiaCaso $\leftarrow$ crearCasoPrueba(casoDePrueba)
				\STATE Conjunto listaProhibida $\leftarrow$  crearConjunto()
				\WHILE{ ( (cantidadeDeVariablesDelCaso $>$ 0) $\wedge$ (clausulasDelCaso $\neq$ $\emptyset$) )}
					\STATE contarApariciones(copiaCaso, listaProhibida)
					\STATE variableQueMasAparecio $\leftarrow$ buscarVarQueMasAparecio(copiaCaso, listaProhibida). //O(V)
					\STATE removerClausulas(copiaCaso, variableQueMasAparecio)
					\STATE agregar \textbf{variableQueMasAparecio} a la listaProhibida 
					\IF{(variableQueMasAparecio $>$ 0)}
						\STATE agregar \textbf{variableQueMasAparecio} a variablesRes	
					\ENDIF
					\STATE cantidadDeVariablesDelCaso $\leftarrow$ cantidadDeVariablesDelCaso - 1
				\ENDWHILE
				\STATE Conjunto clauslasRes = clauslasResultas(casoDePrueba, copiaCaso)
				\STATE int cantClausulasRes = casoDePrueba.cantClausulas - copiaCaso.cantClausulas
				\STATE devolver construirSolucion(cantClausulasRes, clauslasRes , variablesRes)
			\end{algorithmic}
	\end{algorithm}


\subsubsection{Explicaci'on}

Vamos a detallar la tarea que desempe'na cada funci'on especificamente, dado que a pesar de que se intento un pseudoc'odigo compacto y simple, algunos procedimientos auxiliares como variables que no aparece aqu'i merecen de an'alisis particular para entender correctamente el algoritmo con el cual resolvemos computacionalmente nuestra heur'istica. \\

\subsubsection{Observaciones:}
Antes de meternos de lleno en la explicaci'on del anterior pseudoc'odigo, debemos aclarar el uso de 2 variables globales muy importantes y que no aparecen en este por cuestiones de simplicidad.
Usamos dos variables globales, dos arreglos de tuplas, separando variables verdaderas y falsas para agilizar la b'usqueda de dichas variables dentro de las cl'auslas del caso, de aqu'i en adelante los llamaremos \textbf{verdaderos} y \textbf{falsos}. En cada posici'on de dicho arreglo se encuentra una tupla que almacena la cantidad de apariciones de la i-'esima variable en las cl'auslas y en cuales de estas 'ultimas aparece. M'as informlamente hablando: arreglo$<$cantidadAparciones x clausulasDondeAparecio$>$\\
Tener todas esta informaci'on al indexar una posici'on del arreglo nos permite obtener la informacion necesaria de manera eficiente, aunque no debemos olvidar que cargar/ actualizar estos arreglos tiene un costo considerable que detallaremos en la funci'on contarApariciones que es donde dichos arreglos se actualizan permanentemente. \\

\subsubsection{constructivaGolosa}
Este procedimiento hace lo siguiente: realiza un ciclo que repite tantas veces como cantidad de variables de un caso de prueba particular en peor caso(lo describiremos en el an'alisis de complejidad para no complicar la explicaci'on), en cada iteraci'on actualizamos los arreglos \text{verdaderos} y \textbf{falsos} por medio de la funci'on \textbf{contarApariciones} para luego obtener la variable con mayor cantidad de apariciones, esto gracias a la funci'on \textbf{buscarVariableQueMasAparecio} y los mencionados arreglos actualizados, para el conjunto de clausulas existentes en la copia del caso dado que algunas de ellas ser'an eliminadas por contener dicha variable, \textbf{removerClausulas}. Luego mantenemos un lista con aquellas variables con mayor frecuencia dentro de las cl'ausulas para reducir el trabajo de \textbf{contarApariciones} y evitar incongruencias. Por 'ultimo construimos la soluci'on a devolver por la heur'istica, es decir, que cantidad y cuales clausulas fueron satisfechas, el conjunto de literales que producen lo anteior. \\
 
\subsubsection{removerClausulas}
Como bien dice su nombre, esta funci'on elimina aquellas cl'auslas bajo alg'un criterio. Este criterio se basa en borrar toda cl'ausula donde se encuentre la variable con mayor cantidad de apariciones. Para realizar lo mencionado anteriormente, lo primero a realizar es distinguir si dicha variable es verdadera o falsa, de esta forma usaremos alguno de los dos arreglos(\textbf{verdaderos} o \textbf{falsos}) que mencionamos anteriormente. Una vez identificado que arreglo utilizar y obtenidas las clausulas en donde se encuentra la variable por medio del acceso a este en la posici'on correspondiente, lo siguiente a realizar es identificar en que cl'ausulas dicha variable aparece para luego eliminarlas del caso analizado.\\
Esto 'ultimo lo hacemos mediante un ciclo que recorre las cl'ausulas de la copia del caso de prueba que en cada paso del algoritmo principal,  constructivaGoloso, ser'a un conjunto de menor o igual cardinal.

\subsubsection{buscarVariableQUeMasAparecio}
Determina la variable con m'as ocurrencias tiene dentro de las clausulas existentes en la copia del caso de prueba, recordar que este conjunto puede disminuir su cardinal de iteraci'on en iteraci'on. \\
Se recorren los arreglos verdaderos y falsos respectivamente en la busqueda de aquella variable que contenga el valor m'as grande de cantidad de apariciones. Es simplemente una funci'on m'aximo con la salvedad que debemos revisar ambos arreglos.

\subsubsection{contarApariciones}
En esta funci'on se construyen y actualizan los arreglos \textbf{verdaderos} y \textbf{falsos}.\\
Se recorren las clausulas de la copia del caso y para cada una de ellas recorremos sus literales. Si alg'un literal esta prohibido, es decir ya fue una variable con mayor capacidad de apariciones, no actualizamos dicho literal puesto que en este momento no existen clausulas que lo contengan. Para los no prohibidos actualizamos sus valores de cantidad de aparicones y seteamos en que clausula fue hallada, esto lo hacemos distinguiendo variables positivas y negativas.\\

\subsubsection{buscarClausulasResueltas}
Obtiene el conjunto de clausulas safisfechas luego de finalizado el ciclo. Conseguir este conjunto es relativamente simple, recorremos el conjunto de clausulas que quedaron en la copia del caso de prueba verificando que clausulas del caso original no forman parte del mencionado conjunto con lo cual obtenemos aquellas clausulas que fueron satisfechas por alguna de las variables con mayor ocurrencia. \\

\newpage 

\subsection{An'alisis de Complejidad}
Vamos a describir brevemente la operaciones y el costo de los procedimientos auxiliares en primer lugar para luego avocarnos en el algoritmo principal. \\

\textbf{\underline{Notaci'on:}}
\begin{itemize}
	\item Llamamos V al total de variables existentes para el caso de prueba.
	\item Llamamos C al total de cl'ausulas existentes en el caso de prueba.
\end{itemize}

\subsubsection{funci'on contarApariciones}
Al comienzo, crea e incializa los arreglos con tama'no cantidad de variables de un determinado caso. En consecuencia esto tiene costo de V $\in$ O(V). \\
Luego se realizan dos ciclos anidados, uno para recorrer cada cl'ausula del caso y el otro para recorrer los literales contenidos en la cl'ausula correspondiente a la iteraci'on actual, con lo cu'al en una peor situaci'on debemos recorrer sin excepci'on C cl'ausulas, y por cada una, V variables. \\
Ahora bien, dentro del segundo se realizan chequeos para determinar si un variable de una determinada cl'ausula es o no prohibida, esto se realiza con costo constante, O(1), dado que es simplemente chequeaer si la i -'esima variable se encuentra en la i-esima posici'on de la lista prohibida. Teniendo lo anterior resuelto, lo siguiente a realizar es determinar si la variable es positiva o negativa para luego actualizar los valores de cantidad de apariciones como clausulas en las cuales aparece en los arreglos incialmente mencionados, esto 'ultimo tambi'en con costo constante, O(1). \\
Con lo cual podemos concluir que el costo total de esta funci'on es: \\
\begin{enumerate}
	\item{O(V), de crear e inicializar los arreglos \textbf{verdaderos} y \textbf{falsos}}
	\item{O(C * V), la cantidad de iteraciones de los ciclos anidados}
		\begin{itemize}
			\item{recordar que dentro del ciclo, la operaciones realizadas tienen costo constante O(1)}
		\end{itemize}
\end{enumerate}

Con lo cual concluimos que contarApariciones tiene complejidad O(C * V)

\subsubsection{funci'on removerClausulas}
Incialmente verifica si la variable con mayor cantidad de apariciones, \emph{vMax}, es positiva o negativa, para determinar que arreglo debe usar a la hora de obtener las cl'ausulas a suprimir, es decir, \textbf{verdaderos}s o \textbf{falsos}.
Luego se realiza un ciclo sobre las cl'ausulas a las cuales pertenece \emph{vMax}, usando alguno de los arreglos mencionados anteriormente, y borrando dichas cl'ausulas del caso de prueba en cuesti'on. \\
Entonces lo peor que podr'ia ocurrir es que la variable fuera universal, es decir que aparezca en las C cl'ausulas, con lo cual repetimos el ciclo C veces. Dado que dentro de este ciclo, en cada iteraci'on, simplemente se elimina un cl'ausula determinada y se reacomodan punteros para mantener el conjunto de cl'ausulas, el costo que esto conlleva es constante, O(1).\\
Con lo cual podemos concluir que la complejidad de removerClausulas es: O(C).

\subsubsection{funci'on buscarVariableQueMasAparecio}
Esto es simplemente buscar la variable con mayor cantidad de aparciones dentro de los arreglos \textbf{verdaderos} y \textbf{falsos}, tomando el m'aximo entre ellos. Como dichos arreglos tiene longitud V, y los recorremos de manera independiente a cada uno, tenemos V iteraciones. Dentro de cada ciclo simplemente chequeamos valores y swapeamos en caso de actualizar el maximo.
Entonces podemos concluir que esta funci'on tiene una complejidad de O(V).

\subsubsection{funci'on buscarClausulasResultas}
Para las cl'ausulas restantes en la copia del caso de prueba luego de remover o no cl'ausulas. Este procedimiento chequa que cl'ausulas del caso original(sin remover ninguna cl'ausula) no coinciden con las que a'un existen en la copia del caso, es decir, aquellas clausulas que pudieron ser satisfechas por alguna de las variables de la soluci'on y son agregadas a un conjunto de cl'ausulas que luego formara parte de la soluci'on.\\
En el peor contexto, nunca se elimina ninguna cl'ausulas de la copia del caso, con lo cual debemos repetir la verficaci'on mencionada antes C veces. Podemos concluir que el costo de esta funci'on es O(C)

\subsubsection{funci'on constructivaGolosa}
Dado que todas las funciones que se invocan dentro del ciclo fueron analizadas y que fuera del ciclo solo se realizan operaciones constantes exceptuando el llamado a la funci'on buscarClausulasResultas, vamos a concentrarnos en analizar cuantas veces itera el ciclo del algoritmo en el pero contexto posible.\\
Ahora bien, en el ciclo existen dos criterios de corte pero no es evidente a simple vista una cota para la cantidad de veces que el ciclo puede repetirse. Algo sumamente importante a notar es que para analizar el peor caso, debemos asumir que en cada paso del ciclo se eliminan exactamente una cl'ausula. Menos cl'ausulas no se pueden eliminar y eliminar m'as de una por iteraci'on no ser'ia una cota superior en todos los casos a analizar.\\ 

\begin{itemize}
	\item Si V $>$ C
		\begin{itemize}
			\item El ciclo finaliza luego de C iteraciones, con lo cual podemos acotarlo superiormente por V. 
		\end{itemize}
	\item Si V $<$ C
		\begin{itemize}
			\item El ciclo finaliza luego de V iteraciones, dado que V ya no es mayor a 0.
		\end{itemize}
	
	\item Si V $=$ C
		\begin{itemize}
			\item El ciclo finaliza por ambas a la vez, con lo cual itera V = C veces.
		\end{itemize}
\end{itemize}

Luego de este analisis, podemos concluir que la cantidad de veces que se repite el ciclo es V veces. Dentro del ciclo las operaciones significativas son aquellas en las cuales se encuetran involucradas las invocaciones a funciones auxiliares, esto se debe a que son de costo significativamente mayor a las restantes operaciones. \\
Veamos que se ejecuta en el cuerpo del ciclo: \\
\begin{itemize}
 \item{removerClausulas, con costo O(C)}
 \item{contarApariciones, con costo O(C * V)}
 \item{buscarVariableQueMasAparecio, con costo O(V)}
\end{itemize}
Podemos acotar el costo del cuerpo del ciclo como O(C * V) y este se repite V veces.\\
Entonces podemos concluir que la complejidad de la heur'istica constructiva es: \fbox{O(V$^{2}$ * C)}

\newpage

\subsection{Experimentos y Gr'aficos}

\subsubsection{De los casos de prueba}
Para generar cada caso de prueba se tomaron en cuenta las siguientes variables:

\begin{itemize}
	\item Cantidad de cl'asulas
	\item Cantidad de variables
	\item Cantidad de variables por cl'asula 
	\item Cantidad de casos de prueba
	\item Variaci'on en la distribuci'on de variables por cl'ausla
	\item Variaciones en la escala de los ejes en las gr'aficas.
\end{itemize}

La \textit{Cantidad de variables por cl'asula} es generada al azar por un m'etodo de la plataforma Java 2, versi'on 6, que, seg'un su javadoc(\textbf{Returned values are chosen pseudorandomly with (approximately) uniform distribution from that range}) los valores rand'omicos provienen de una distribuci'on aproximadamente uniforme.\\
La \textit{Cantidad de variables}, \textit{Cantidad de cl'ausulas} y \textit{Cantidad de casos de prueba} son fijadas de antemano para generar los casos de prueba y sus diferentes variantes.\\
Tambi'en usamos un random a la hora de distribuir las variables en las cl'ausulas, esto para tener conjuntos de casos de pruebas bien diferenciados y poder apreciar as'i el comportamiento del algoritmo realizado en esta etapa. \\
Las escalas elegidas para estos gr'aficos en general son logar'itmicas para el eje que cuenta operaciones para apreciar la diferencia entre las funciones graficadas. Muchos casos de prueba resultaron poco informativos porque la diferencia entre la complejidad te'orica y la calculada emp'iricamente era demasiado grande, obteniendo valores muy alejados y apreciando s'olo una funci'on y no la comparaci'on entre ambas.\\
Para medir emp'iricamente la complejidad se contaron operaciones en el c'odigo fuente. \\
La complejidad te'orica, en los gr'aficos, esta multiplicada por una constante.\\
Vamos a analizar diversos casos y a discriminar el peor caso para este algoritmo, que detallado en el an'alisis realizado para el c'alculo de la complejidad teorica.\\

\newpage

\subsubsection{Gr'aficos complejidad te'orica vs Complejidad medida en la pr'actica}

{\ttfamily \large{Experimento n'umero 1:}}

	\begin{itemize}
		\item Cantidad de cl'asulas: 50
		\item Cantidad de variables: 24
		\item Cantidad de casos de prueba: 50
		\item Graficos que representa cantidad de operaciones respecto a cantidad de variables.
		\item Se generan 2 gr'aficos para poder apreciarse de diferentes perspectivas, uno donde el eje de las ordenas tenga escala logaritmica y otro donde su escala en el eje $y$ no es alterada.
	\end{itemize}

{\ttfamily \underline{An'alisis de los gr'aficos}}
\newline
\newline
Parece correcta la elecci'on de la escala logaritmica para poder apreciar muy claramente como el valor complejidad te'orica multiplicada por una constante adecuada acota superiormente los valores de cantidad de operaciones obtenidos emp'iricamente para cada caso de prueba en cuesti'on.\\
Respecto a la gran diferencia existente de valores te'oricos y emp'iricos usando la escala normal en el eje $y$, notamos que es producido debido a que en gran cantidad de juegos de casos de prueba la distribuci'on de variables dentro de las cl'ausulas era lo suficientemente buena como para que el algoritmo terminar'a su ejecuci'on luego de una escasa cantidad de iteraciones en contraste con lo esperado te'oricamente. Esto ocurre en casos de prueba donde una pequeña cantidad de variables aparece en la mayoría de las cl'ausulas, con lo cu'al cuando obtengamos aquella con mayor aparici'on dentro de las cl'ausulas y eliminemos estas, nos quedamos con un conjunto reducido de cl'ausulas ya que en un s'olo paso eliminamos un gran n'umero de ellas.\\
Esto pudimos inferirlo luego de un an'alisis minucioso de los casos de prueba generados para realizar las gr'aficas y de un seguimiento exhaustivo del algoritmo.\\
Con lo cual, usando la escala normal no podemos percibir como se comportan las cotas para una determinada cantidad de casos  

\begin{figure}[H]
	\begin{center}
		\includegraphics[width=0.9\textwidth]{dibujos/HeuristicaConstructiva/Complejidad/Constr_50_clas_24_vars_12_Rand_50_Casos_escala_log.png}
	\end{center}
	\begin{center}
		\includegraphics[width=0.9\textwidth]{dibujos/HeuristicaConstructiva/Complejidad/Constr_50_clas_24_vars_12_Rand_50_Casos_escala_normal.png}
	\end{center}
\end{figure}

\newpage

{\ttfamily \large{Experimento n'umero 2:}}

\begin{itemize}
	\item Cantidad de cl'asulas: 1000
	\item Cantidad de variables: 49
	\item Cantidad de casos de prueba: 10
	\item Se generan 2 gr'aficos para poder apreciarse de diferentes perspectivas, uno donde el eje de las ordenas tenga escala logaritmica y otro donde su escala en el eje y no es alterada.
\end{itemize}

{\ttfamily \underline{An'alisis de los gr'aficos}}
\newline
\newline
Nuevamente podemos comentar lo mismo que en el caso anterior, con la salvedad que se aumentar la cantidad de cl'ausulas con el objetivo de producir una distribuci'on de variable menos favorable para el algoritmo y poder as'i observar como se comportan las cotas sin tener que alterar las escalas. Producida esta situaci'on, volvimos a alterar la escala del eje $y$ y pudimos apreciar el comportamiento de las cotas, confirmando que el an'alisis te'orico del algoritmo es correcto. El beneficio de usar la escala logaritmica en estos casos es que a pesar de existir una gran diferencia en los valores te'oricos y emp'iricos para un determinado caso de prueba, la funci'on logar'itmica crece sumamente lento por lo que a valores muy grandes los transforma en valores realmente pequeños logrando as'i una visualizaci'on m'as provechosa. De todas formas no hay que olvidar el motivo por el cual de produce esta diferencia tan significativa entre ambas cotas, lo cual nuevamente es producido por el motivo anterior.

\begin{figure}[H]
	\begin{center}
		\includegraphics[width=0.9\textwidth]{dibujos/HeuristicaConstructiva/Complejidad/Constr_1000_clas_49_vars_8_Rand_10_Casos_escala_log.png}
	\end{center}
	\begin{center}
		\includegraphics[width=0.9\textwidth]{dibujos/HeuristicaConstructiva/Complejidad/Constr_1000_clas_49_vars_8_Rand_10_Casos_escala_normal.png}
	\end{center}

\end{figure}

\newpage


{\ttfamily \large{Experimento n'umero 3:}}

\begin{itemize}
	\item Cantidad de cl'asulas: 400
	\item Cantidad de variables: 70
	\item Cantidad de casos de prueba: 10
	\item Se generan 2 gr'aficos para poder apreciarse de diferentes perspectivas, uno donde el eje de las ordenas tenga escala logaritmica y otro donde su escala en el eje y no es alterada.
\end{itemize}


{\ttfamily \underline{An'alisis de los gr'aficos}}
\newline
\newline
En estos dos 'ultimos gr'aficos podemos apreciar lo esperado, nuevamente realizamos las variaciones de las escalas propuestas al comienzo de la secci'on aunque esta vez la escala logaritmica es tan provechosa como la escala normal.\\
La diferencia y el porque del an'alisis de este 'ultimo radica en que fue generado un peor caso para nuestro algoritmo y pareci'o muy importante observar su comportamiento. \\
Para esta caso se generaron 400 cl'ausulas con 70 variables como m'aximo valor posible por cada una de las primeras, pero con la gran diferencia de que distribuimos las variables de forma de que una variable se repitiera en un porcentaje peque'no de cl'ausulas para conseguir que el ciclo algoritmo se repita aproximadamente la cantidad de veces an'alisada te'oricamente con lo cual podr'iamos observar un comportamiento similar en las cotas. En otras palabras generamos un caso de forma que si o si sea un caso malo para el algoritmo.\\
Observando ambos graficos y ,en contraste con los dos casos anteriores, podemos concluir que conseguimos nuestro objetivo para este experimiento an'alisado como as'i tambi'en respecto al c'alculo de la complejidad.

\begin{figure}[H]
	\begin{center}
		\includegraphics[width=0.9\textwidth]{dibujos/HeuristicaConstructiva/Complejidad/nuevas/Constr_100_clas_50_vars_50_Rand_10_Casos_escala_log.png}
	\end{center}
	\begin{center}
		\includegraphics[width=0.9\textwidth]{dibujos/HeuristicaConstructiva/Complejidad/nuevas/Constr_100_clas_50_vars_50_Rand_10_Casos_escala_normal.png}
	\end{center}

\end{figure}

\newpage
\subsubsection{Comparaci'on de resultados Algoritmo Exacto vs Heur'istica Constructiva}
Para analizar los resultados de las t'ecnicas utilizadas se corrieron diferentes casos de prueba, generados aleatoriamente con las mismas variables (cantidad de variables, cantidad de casos de prueba, distribuci'on de variables por cl'ausula) que para medir la complejidad. \\
En el eje vertical est'a el resultado obtenido. En el eje horizontal el n'umero de caso de prueba, simplemente para identificar cada caso con un n'umero y diferenciarlo del resto. Si se trazara una linea vertical se podr'ia comparar los resultados para los diferentes algoritmos. Intentamos observar cuan alejados estan los resultados para los diferentes algoritmos.

\begin{itemize}
	\item Cantidad de cl'asulas: 100
	\item Cantidad de variables: 15
	\item Cantidad de casos de prueba: 6
\end{itemize}

\begin{figure}[H]
	\begin{center}
		\includegraphics[width=0.9999\textwidth]{dibujos/HeuristicaConstructiva/Comparaciones_entre_algoritmos/100_cla_15_var_6_casodeprueba_6_random.png}
	\end{center}
\end{figure}

\begin{itemize}
	\item Cantidad de cl'asulas: 50
	\item Cantidad de variables: 15
	\item Cantidad de casos de prueba: 4
\end{itemize}

\begin{figure}[H]
	\begin{center}
		\includegraphics[width=0.9999\textwidth]{dibujos/HeuristicaConstructiva/Comparaciones_entre_algoritmos/50_cla_15_var_4_casodeprueba_9_random.png}
	\end{center}
\end{figure}

\underline{An'alisis de los gr'aficos:}
Podemos notar, en ambos gr'aficos, que en un gran porcentaje de casos de prueba que tanto la heur'istica constructiva como el algoritmo exacto consiguen satisfacer igual n'umero de cl'ausulas. Tambi'en podemos percibir en otros como la heuristica consigue una soluci'on aproximada respecto a la soluci'on obtenida por el algoritmo exacto, pero que en ninguno de los casos analizados notamos un diferencia muy signifativa. En los caso donde se puede percibir dicha diferencia, nunca es mayor a 10 a las cla'usulas. \\
Con lo cual para los casos analizados podemos concluir que la heur'istica tiene una buena performance respecto a su complejidad y tiempo de ejecuci'on como as'i tambi'en en los resultados que obtiene. 

\subsection{Conclusiones}

Luego de resuelto el algoritmo y realizado los an'alisis correspondientes, tanto de complejidad como de pruebas podemos concluir que se consiguio' el compromiso planteo de rendimiento/calidad de soluciones propuestos para la heur'istica. Tambi'en pudimos apreciar que para obtener soluciones considerablemente buenas en la mayor'ia de los casos, pero no las 'optimas, reducen significativamente la dificultad de implementaci'on/resoluci'on que conlleva un algoritmo que de una soluci'on exacta. Todo esto basandonos en ideas simples e intuitivas, pero estudiando detenidamente que estructuras de datos eran convenientes a la hora de la implementaci'on para luego conseguir resultados aceptables con un costo polinomial.